package com.leetcode.周赛.第227场;

/**
 * @author: ZhouBert
 * @date: 2021/2/7
 * @description: 5674. 构造字典序最大的合并字符串
 * https://leetcode-cn.com/contest/weekly-contest-227/problems/largest-merge-of-two-strings/
 */
public class B_5674_构造字典序最大的合并字符串 {

	public static void main(String[] args) {
		String word1 = "cabaa";
		word1 = "guguuuuuuuuuuuuuuguguuuuguug";
		String word2 = "bcaaa";
		word2 = "gguggggggguuggguugggggg";
		B_5674_构造字典序最大的合并字符串 action = new B_5674_构造字典序最大的合并字符串();
		String res = action.largestMerge(word1, word2);
	}

	/**
	 * 这个似乎就是归并排序，而且不难的。
	 *
	 * @param word1
	 * @param word2
	 * @return
	 */
	public String largestMerge(String word1, String word2) {
		char[] w1chars = word1.toCharArray();
		int len1 = w1chars.length;
		char[] w2chars = word2.toCharArray();
		int len2 = w2chars.length;
		//结果数组
		char[] reschars = new char[len1 + len2];
		int index1 = 0, index2 = 0;
		int index = 0;
		boolean firstBigger = true;
		while (index1 < len1 && index2 < len2) {
			if (w1chars[index1] == w2chars[index2]) {
				//如果相等，就需要看哪个字典大的 离得更近
				int tempIndex1 = index1 + 1;
				int tempIndex2 = index2 + 1;
				while (tempIndex1 < len1 && tempIndex2 < len2) {
					char c1 = w1chars[tempIndex1];
					char c2 = w2chars[tempIndex2];
					if (c1 > c2) {
						firstBigger = true;
						break;
					} else if (c1 < c2) {
						firstBigger = false;
						break;
					}
					tempIndex1++;
					tempIndex2++;
				}
				if (tempIndex1 == len1) {
					//如果已经消耗完了
					firstBigger = false;
				} else if (tempIndex2 == len2) {
					firstBigger = true;
				}
				if (firstBigger) {
					reschars[index] = w1chars[index1++];
				} else {
					reschars[index] = w2chars[index2++];
				}
				index++;
				continue;
			}
			if (w1chars[index1] > w2chars[index2]) {
				reschars[index] = w1chars[index1++];
			} else {
				reschars[index] = w2chars[index2++];
			}
			index++;
		}
		if (index1 == len1) {
			//如果 w1 已经消耗完
			while (index2 < len2) {
				reschars[index++] = w2chars[index2++];
			}
		}
		if (index2 == len2) {
			//如果 w2 已经消耗完
			while (index1 < len1) {
				reschars[index++] = w1chars[index1++];
			}
		}
		return new String(reschars);
	}
}
